package leetcode

import "math"

/*
 * @lc app=leetcode.cn id=931 lang=golang
 *
 * [931] 下降路径最小和
 */

// @lc code=start
func MinFallingPathSum(rc [][]int) int {
	minValue := math.MaxInt
	n := len(rc)
	dp := make([][]int, n)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n)
	}
	for layer := n - 1; layer >= 0; layer-- {
		if layer == n-1 {
			dp[layer] = rc[layer]
			continue
		}

		for position := 0; position < len(dp[layer]); position++ {
			var current = dp[layer+1][position]
			if position != 0 && current > dp[layer+1][position-1] {
				current = dp[layer+1][position-1]
			}
			if position != len(rc[layer])-1 && current > dp[layer+1][position+1] {
				current = dp[layer+1][position+1]
			}
			dp[layer][position] = rc[layer][position] + current
		}
	}

	for _, v := range dp[0] {
		if v < minValue {
			minValue = v
		}
	}

	return minValue
}

// @lc code=end
